CSP2020 快到了,感觉自己 dp 太菜了,补了很多 dp >_<
题意(经过 OI 化魔改):给定一棵二叉树,每次可以交换一个节点的左右儿子,使这棵二叉树是完全二叉树。
思路:容易想到如下几种情况。
情况 :容易想到,若所有叶子节点中最深的深度和最浅的深度之差大于 ,那么无解,因为此时没有办法通过交换左右儿子将深度差减少。
情况 :如果所有叶子深度均相同,直接输出 。
以上情况可以通过一遍 dfs 求深度解决。
情况 :对于一个节点,如果左子树全部为深度浅的节点,且右子树存在深度深的节点,此时需要进行一次交换。
情况 :对于一个节点,如果左子树存在深度深、浅的两种节点,且右子树全部为深度深的节点,此时需要进行一次交换。
情况 :对于一个节点,如果左、右子树均存在深度深、浅的两种情况,那么无解,因为无论怎么交换,总存在左子树的深度浅的节点比右子树的深度深的节点不符合题意。
以上情况在第二遍 dfs 时统计。
实现细节:第一遍 dfs 就是正常的求深度,没什么好说的,主要说说第二遍 dfs。
第二遍 dfs 的返回值设计为 ,分别表示当前结点为根的子树全部为深度浅的节点、深度深的节点,或者二者皆有。在递归返回的时候,我们判断左、右子树返回值进行处理即可。
代码:
//By: Luogu@rui_er(122461)
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+5, inf = 0x3f3f3f3f;
int n, son[N][2], mi = inf, ma, ans;
void dfs(int u, int k) {
if(u == -1) return (mi=min(mi, k)), (ma=max(ma, k)), void();
dfs(son[u][0], k+1);
dfs(son[u][1], k+1);
}
int dfs2(int u, int k) {
if(u == -1) return (k != mi);
int x = dfs2(son[u][0], k+1);
int y = dfs2(son[u][1], k+1);
ans += ((!x && y) || (x == 2 && y == 1));
if(x == 2 && y == 2) exit((puts("-1"), 0));
if(x == 2 || y == 2 || x + y == 1) return 2;
if(!(x + y)) return 0;
return 1;
}
int main() {
scanf("%d", &n);
for(int i=1;i<=n;i++) scanf("%d%d", &son[i][0], &son[i][1]);
dfs(1, 0);
if(ma - mi > 1) return puts("-1"), 0;
if(ma == mi) return puts("0"), 0;
int _ = dfs2(1, 0);
printf("%d\n", ans);
return 0;
}